package com.cb2.algorithm.leetcode;

import java.util.PriorityQueue;

/**
 * <a href='https://leetcode.cn/problems/find-median-from-data-stream/'>数据流的中位数(Find Median from Data Stream)</a>
 * <p>中位数是有序整数列表中的中间值。如果列表的大小是偶数，则无中间值，中位数是两个中间值的平均值。例如：
 * <ul>
 *     <li>arr = [2,3,4] 的中位数是 3 。</li>
 *     <li>arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。</li>
 * </ul>
 * </p>
 * <p>
 * 实现 MedianFinder 类:
 * <ul>
 *     <li>MedianFinder() 初始化 MedianFinder 对象。</li>
 *     <li>void addNum(int num) 将数据流中的整数 num 添加到数据结构中。</li>
 *     <li>double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。</li>
 * </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例：
 *      输入
 *          ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
 *          [[], [1], [2], [], [3], []]
 *      输出
 *          [null, null, null, 1.5, null, 2.0]
 *      解释
 *          MedianFinder medianFinder = new MedianFinder();
 *          medianFinder.addNum(1);    // arr = [1]
 *          medianFinder.addNum(2);    // arr = [1, 2]
 *          medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
 *          medianFinder.addNum(3);    // arr[1, 2, 3]
 *          medianFinder.findMedian(); // return 2.0
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>-10^5 <= num <= 10^5</li>
 *     <li>在调用 findMedian 之前，数据结构中至少有一个元素</li>
 *     <li>最多 5 * 10^4 次调用 addNum 和 findMedian</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/12/16 14:12
 */
public class LC0295FindMedianFromDataStream_H {

    static class MedianFinder {
        /**
         * 大根堆：用于保存较小的一半元素。如果是偶数个，保存n/2，如果是奇数个，保存n/2 +1。
         */
        PriorityQueue<Integer> firstHeap;
        /**
         * 小根堆：用于保存较大的一半元素。如果是偶数个，保存n/2，如果是奇数个，保存n/2。
         */
        PriorityQueue<Integer> secondHeap;


        public MedianFinder() {
            firstHeap = new PriorityQueue<>((e1, e2) -> e2 - e1);
            secondHeap = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if (firstHeap.size() == secondHeap.size()) {    // 最终添加到firstHeap中
                secondHeap.add(num);
                firstHeap.add(secondHeap.poll());
            } else {                                         // 最终添加到secondHeap中
                firstHeap.add(num);
                secondHeap.add(firstHeap.poll());
            }
        }

        public double findMedian() {
            if (firstHeap.size() == secondHeap.size()) {
                return (firstHeap.peek() + secondHeap.peek()) / 2.0;
            }
            return firstHeap.peek();
        }
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());  // 1.5
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());  // 2.0
    }
}
